package november.sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/11/18-21:27
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        long timeMillis1 = System.currentTimeMillis();

        insertSort2(arr);
        long timeMillis2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));


        System.out.println(timeMillis2 - timeMillis1);
    }


    private static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //有序表
            for (int j = 0; j <= i; j++) {
                //arr[i+1]为无序表中的第一个元素
                int insertIndex = i + 1;//记录要插入的元素索引
                int insertValue = arr[i + 1];//记录要插入的元素
                if (arr[j] > insertValue) { //如果有序表中的元素>无序表中的元素,则进行插入操作
                    int index = insertIndex;
                    //元素后移腾出位置给插入的元素
                    while (index != j) {
                        arr[index] = arr[index - 1];
                        index--;
                    }
                    arr[j] = insertValue;//插入元素
                    break;
                }
            }
        }
    }


    /**
     * 推荐这种
     * @param arr
     */
    private static void insertSort2(int[] arr) {
        for (int i = 1; i < arr.length - 1; i++) {
            //无序表
            int insertIndex = i - 1;//插入的坐标(有序表最后一个)
            int insertValue = arr[i];//待插入的数(无序表第一个)
            //无序表与(有序表元素从尾到头)进行比较 , 直到找到比无序表第一个元素小的 有序表元素
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                //比较的同时也进行元素后移
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                //找到要插入的位置进行插入
                arr[insertIndex + 1] = insertValue;
            }
        }
    }
}
